#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/5/10 8:57
# ===========================================
#       题目名称： 41. 缺失的第一个正数
#       题目地址： https://leetcode.cn/problems/first-missing-positive/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:
    """
        给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
        请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
    """

    def firstMissingPositive(self, nums):
        nums.sort()
        minUnsigned = 1
        for i in range(len(nums)):
            if nums[i] == minUnsigned:
                minUnsigned += 1
        return minUnsigned


if __name__ == "__main__":
    s = Solution()
    print(s.firstMissingPositive(nums=[1, 2, 0]))  # 3
    print(s.firstMissingPositive(nums=[3, 4, -1, 1]))  # 2
    print(s.firstMissingPositive(nums=[7, 8, 9, 11, 12]))  # 1
